#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int sz = mat.size();
        vector<vector<int>> vv(sz + 1);
        vv[0].resize(mat[0].size() + 1, 0);

        for (int i = 1; i < vv.size(); i++)
        {
            vv[i].resize(mat[0].size() + 1, 0);
            for (int j = 1; j < vv[0].size(); j++)
            {
                vv[i][j] = vv[i - 1][j] + vv[i][j - 1] + mat[i - 1][j - 1] - vv[i - 1][j - 1];
            }
        }

        // for(int i = 0;i<vv.size();i++)
        // {
        //     for(int j = 0;j<vv[0].size();j++)
        //     {
        //         cout<<vv[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }

        vector<vector<int>> answer(sz);
        for (int i = 0; i < sz; i++)
        {
            answer[i].resize(mat[0].size(), 0);
            for (int j = 0; j < mat[0].size(); j++)
            {
                if ((i + k >= sz))
                {
                    answer[i][j] = vv[i + 1][j + 1 + k] - vv[i + 1 - k - 1][j + 1 + k];
                }
                else if (j + k >= mat[0].size())
                {
                    answer[i][j] = vv[i + 1 + k][j + 1] - vv[i + 1 + k][j + 1 - k - 1];
                }
                else if (i + k >= sz && j + k >= mat[0].size())
                {
                    answer[i][j] = vv[i + 1 + k][j + 1 + k] - vv[i + 1 - k - 1][j + 1 + k] - vv[i + 1 + k][j + 1 - k - 1]
                        ;
                }
                else
                    answer[i][j] = vv[i + k + 1][j + k + 1];
            }
        }
        return answer;

    }
};